package top.minuy.structure.graph.search.depth.dfs;

import top.minuy.structure.graph.representations.table.Graph;

import java.util.ArrayList;
import java.util.List;

/**
 * 对图的深度优先遍历
 * 增加先序，后序遍历
 *
 * @author Minuy
 * @time 11:34
 * @date 2021/11/16
 */
public class GraphDFSV3 {

    // int n = 0;

    private Graph g;
    private boolean[] isVisited;

    private List<Integer> pre, post;

    public GraphDFSV3(Graph g) {
        this.g = g;
        this.isVisited = new boolean[g.V()];

        pre = new ArrayList<>();
        post = new ArrayList<>();

        // 遍历所有联通分量
        for (int v = 0; v < g.V(); v++) {
            if (!isVisited[v]) {
                order(v);
            }
        }
    }

    private void order(int v) {
        isVisited[v] = true;

        pre.add(v);  // 先序遍历

        for (Integer w : g.adj(v)) {
            // System.out.println("执行次数："+(++n));
            if (!isVisited[w]) {
                order(w);
            }
        }

        post.add(v); // 后序遍历
    }

    public Iterable<Integer> pre() {
        return pre;
    }

    public Iterable<Integer> post() {
        return post;
    }
}
